package leetcode.weekly.week330;

//Solution2Test
public class Solution21 {

//	return (BigInteger.TWO.modPow(BigInteger.valueOf(n), BigInteger.valueOf(1000000007)).intValue() + 1000000005)
//			% 1000000007;

	int mod = (int) 1e9 + 7;

	public int monkeyMove(int n) {
		long ans = pow(2, n);
		return (int) ((ans - 2 + mod) % mod);
	}

	private long pow(int basic, int n) {
		if (n == 0) {
			return 1;
		}
		long b = pow(basic, n >> 1);
		long bb = b * b % mod;
		return (n & 1) == 1 ? bb * basic % mod : bb;
	}

}
